package com.sparsearr.datastructures.ztr.tree;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import java.util.Arrays;

/**
 * @Author: ZhaoTR
 * @Date: Created in 2025/7/2 20:53
 * @Description: 堆排序
 * @Version: 1.0
 */

public class HeapSort {
    private static final Logger logger = LogManager.getLogger(HeapSort.class);

    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
    }

    /**
     * 堆排序
     *
     * @param arr 待排序的数组
     */
    public static void heapSort(int[] arr) {
        int temp = 0;
//        adjustHeap(arr, 1, arr.length);
//        logger.info("第一次排序后的数组为：{}", Arrays.toString(arr));
//
//        adjustHeap(arr, 0, arr.length);
//        logger.info("第二次排序后的数组为：{}", Arrays.toString(arr));

        for (int i = arr.length / 2 -1 ; i > 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println("第三次排序后的数组为：" + Arrays.toString(arr));
    }

    /**
     * 将一个数组（二叉树）调整成一个大顶堆
     * 完成将以 i 对应的非叶子节点的数调整成大顶堆
     *
     * @param arr    待调整的数组
     * @param i      非叶子节点的索引
     * @param length 数组大小，length 是逐渐的在减少
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        // 获取当前非叶子节点的元素值
        int temp = arr[i];
        // k 指的是非叶子节点的左子节点  k * 2 + 1 是i节点的左子节点
        for (int k = i * 2 + 1; k < arr.length; k = k * 2 + 1) {
            // 说明左子节点小于右子节点
            if (arr[k] < length && arr[k] < arr[k + 1]) {
                // k 指的是右子节点
                k++;
            }
            // 如果当前非叶子节点的元素小于子节点的元素，则交换元素位置
            if (arr[k] > temp) {
                // 把较大的赋值给当前非叶子节点的元素
                arr[i] = arr[k];
                // 继续循环，交换位置
                i = k;
            } else {
                break;
            }
        }
        // 当循环结束后，i 的值，就是当前非叶子节点的元素，应该存放的位置
        arr[i] = temp;
    }
}
